package tu.bianli;

import tu.juzheng.IGraph;
import tu.bianli.queue.*;

public class Tu_BFS {
    private static boolean[] visited;       //访问标志数组
    //对图G做广度优先遍历
    public static void BFSTraverse(IGraph G) throws Exception{
        visited = new boolean[G.getVexNum()];       //访问标志数组
        for (int v = 0; v < G.getVexNum(); v++) {
            //访问标志数组初始化
            visited[v] = false;
        }
        for (int v = 0; v < G.getVexNum(); v++) {
            if(!visited[v]){                 //v尚未访问
                BFS(G, v);
            }
        }
    }

    public static void BFS(IGraph G, int v)throws Exception{
        visited[v] = true;
        System.out.print(G.getVex(v).toString() + " ");
        LinkQueue Q = new LinkQueue();        //辅助队列
        Q.offer(v);
        while(!Q.isEmpty()){
            int u = (Integer) Q.poll();         //队头元素出队列并赋值给u
            for (int w = G.firstAdjVex(u); w >= 0; w = G.nextAdjVex(u, w)) {
                if(!visited[w]){
                    visited[w] = true;
                    System.out.println(G.getVex(w).toString() + " ");
                    Q.offer(w);
                }
            }
        }
    }
}
